import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution229 {
    public List<Integer> majorityElement(int[] nums) {
        int count1 = 0, ele1 = 0, count2 = 0, ele2 = 0, n = nums.length;
        for (int num:nums) {
            if(count1 >= 0 && ele1 == num){
                count1++;
            }
            else if(count2 >= 0 && ele2 == num){
                count2++;
            }
            else if(count1 == 0){
                ele1 = num;
                count1++;
            }
            else if(count2 == 0){
                ele2 = num;
                count2++;
            }
            else{
                count1--;
                count2--;
            }
        }
        count1 = 0; count2 = 0;
        for (int num:nums) {
            if(num == ele1) count1++;
            else if(num == ele2) count2++;
        }
        List<Integer> res = new ArrayList<>();
        if(count1 > n / 3){
            res.add(ele1);
        }
        if(count2 > n / 3){
            res.add(ele2);
        }
        return res;
    }

    public static void main(String[] args) {
        Solution229 s = new Solution229();
        System.out.println(s.majorityElement(new int[]{2,1,1,3,1,4,5,6}));
    }
}